The present invention relates generally to the field of estimating the vanishing points of an image. More specifically, the present invention relates to applying a method to accurately locate the vanishing point.
A vanishing point is a result of the perspective projection of a three dimensional scene onto a two dimensional image plane. A vanishing point refers to the point in the image plane (that is, a two dimensional projection of the three dimensional scene) where parallel lines in the scene meet. Vanishing points generally only have relevance for images containing a structure having at least two line segments. Consequently, line segments that are relevant to vanishing points may be constructed from images that include man-made structures.
Vanishing point detection in the field of camera technology is important because detecting the vanishing point of an image can be a significant first step in correcting for image rotation caused by a user""s inability to hold the camera level. Several ideas and methods on how to detect vanishing points have been proposed and attempted.
Barnard, in xe2x80x9cInterpreting Perspective Imagesxe2x80x9d, Artificial Intelligence, vol. 21 first proposed the idea of using a Gaussian sphere as an accumulator space for vanishing point detection. The xe2x80x9cplane of interpretationxe2x80x9d is identified as the plane passing through the center of the sphere (the origin or focal point of the optical system) and both ends of a particular line segment. Each bin of the Gaussian sphere accumulator that falls on the intersection of the Gaussian sphere and the interpretation plane (this intersection forms a great circle) is incremented. After this procedure is completed for all line segments, the vanishing points may be found by searching for local maxima on the sphere. The position of the local maximum represents the vanishing point vector. The location of the vanishing point in the image plane may be determined by projecting this vector back onto the image plane. One difficulty with Barnard""s approach is that the partitioning of the Gaussian sphere causes non-uniform bin sizes that affect the final results.
Magee and Aggarwal, in xe2x80x9cDetermining Vanishing Points From Perspective Images,xe2x80x9d Computer Vision, Graphics, and Image Processing, vol. 26 propose a vanishing point detection scheme that is similar to Barnard""s method, primarily because a Gaussian sphere is again utilized. However, in this method the Gaussian sphere is not used as an accumulator. In the Magee and Aggarwal method, cross products operations are performed in order to identify the intersections of line segments on the Gaussian sphere, and afterwards a list of all intersections of each pair of line segments is collected. A clustering operation is performed to find common intersections that are identified as possible vanishing points. Also, Magee and Aggarwal show that the algorithm is insensitive to focal length. Their method has several advantages. First, the accuracy of the estimated vanishing point is not limited to the quantization of the Gaussian sphere. Second, Magee and Aggarwal consider each intersection individually. Therefore, an intersection that is not feasible (for example, an intersection that occurs within the endpoints of one of the two component line segments) as a vanishing point may be rejected. This selection of feasible vanishing points is not possible with the accumulator space method of Barnard or Brillault and O""Mahony, which consider only line segments rather than intersections.
Lutton, Maitre, and Lopez-Krahe in xe2x80x9cContribution to the Determination of Vanishing Points Using Hough Transform,xe2x80x9d IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, no. 4 introduced a probability mask on the Gaussian sphere in order to compensate for the finite extent of the image. In Barnard""s algorithm, the great circle associated with every line segment passes through the projection of the image onto the sphere. This makes the algorithm more likely to detect a vanishing point that falls within the image than outside of the image. The probability mask attempts to account for this effect by considering the probability of two random lines (i.e., noise) intersecting at any given place on the Gaussian sphere. However, the authors fail to take into consideration the prior probability of the actual vanishing point locations, and instead assume that all vanishing points are equally likely. This assumption is far from the actual case. In addition, the authors describe an effort to account for errors in line segment identification. Rather than incrementing only the bins falling on the great circle, the authors propose incrementing the bins falling in a swath about the great circle.
The swath size is determined by possible interpretation planes passing through the endpoints of the line segments. Consequently, longer line segments that have a higher degree of certainty, will cause incrementalism over a more narrow swath on the Gaussian sphere. A weight based on the line length is distributed evenly among all bins contained in the swath. However, this weighting scheme is based upon assumption rather than actual ground truth data. As an additional algorithm feature, three vanishing points corresponding with the three orthogonal dimensions are simultaneously detected. This feature adds robustness for scenes containing all dimensions, although, many scenes contain structure without containing all three dimensions. Additionally, this algorithm feature requires the use of an accurate focal length. Finally, this algorithm cannot calculate any single intersection of two line segments, thus omitting some of the advances made by Magee and Aggarwal.
Therefore, a need exists for overcoming the above-described drawbacks. In particular, a need exists for a method to determine the most likely vanishing point location while considering the collection of numerous intersections and conditional probabilities.
The above noted need is met according to the present invention by providing a method of determining a vanishing point related to an image, the method includes the steps of: detecting line segments in the image; determining intersections from pairs of line segments; assigning a probability to each intersection of the pairs of line segments; determining a local maximum corresponding to a plurality of probabilities; and outputting an estimated vanishing point vector xcexdE that corresponds to the determined local maximum such that an estimated location of the vanishing point about the estimated vanishing point vector xcexdE results.
As a new approach to vanishing point detection, ground truth data is utilized to establish conditional probabilities in a cross product scheme similar to Magee""s. Features pertaining to the two line segments forming each intersection are used to determine the conditional probability that the intersection is coincident to a ground truth vanishing point. Weighted clustering is then performed to determine the most likely vanishing point location, considering the collection of intersections and conditional probabilities. This algorithm is based upon the ground truth vanishing point data derived from the 86 images in a training set. This algorithm represents the first reported use of ground truth data for training an automatic vanishing point detection algorithm.
These and other aspects, objects, features and advantages of the present invention will be more clearly understood and appreciated from a review of the following detailed description of the preferred embodiments and appended claims, and by reference to the accompanying drawings.